package com.dylan.历史.算法.排序;

import com.dylan.历史.util.LogUtil;

import java.util.Arrays;

/**
 * Created by Dylan on 2018/10/23.
 */
public class 基础_排序_快速排序 {

    public static void main(String[] args) {
        LogUtil.info(Arrays.toString(quickSort(new int[]{3, 6, 2, 7, 2, 6, 8, 0})));
    }

    static int[] quickSort(int[] arr) {
        int l = 0;
        int r = arr.length - 1;
        quickSort(arr, l, r);
        return arr;
    }

    /**
     * 快速排序算法 O(nlogn)
     * 以x为标识，使左边部分都小于x，右边部分都大于x
     * 然后分别迭代左右两部分
     */
    static void quickSort(int[] arr, int l, int r) {
        if (l < r) {
            int i = l;
            int j = r;
            int x = arr[l];
            while (i < j) {
                while (i < j && arr[j] >= x) {
                    j--;
                }
                if (i < j) {
                    arr[i] = arr[j];
                }
                while (i < j && arr[i] <= x) {
                    i++;
                }
                if (i < j) {
                    arr[j] = arr[i];
                }
            }
            arr[i] = x;
            quickSort(arr, l, i - 1);
            quickSort(arr, i + 1, r);
        }
    }
}
